package com.cqs.leetcode.backtrack;

import com.google.common.collect.Lists;
import org.omg.PortableInterceptor.INACTIVE;

import java.util.*;
import java.util.function.ToIntFunction;

/**
 * lixw
 * 2020/11/1
 **/
public class WordBreakII140 {


    //超时

    /**
     * "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
     * ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
     */
    static class Solution {
        private List<String> result = new ArrayList<>();

        public List<String> wordBreak(String s, List<String> wordDict) {
            //result = new ArrayList<>();
            Set<String> dict = new HashSet<>(wordDict);
            backtrack(s, dict, new ArrayList<>());
            return result;
        }

        private void backtrack(String words, Set<String> dict, List<String> tmp) {
            if (words.length() == 0) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < tmp.size(); i++) {
                    if (i != 0) {
                        sb.append(" ");
                    }
                    sb.append(tmp.get(i));
                }
                result.add(sb.toString());
                return;
            }
            for (int i = 1; i <= words.length(); ++i) {
                String word = words.substring(0, i);
                if (!dict.contains(word)) continue;
                //加入
                tmp.add(word);
                backtrack(words.substring(i), dict, tmp);
                //回溯
                tmp.remove(tmp.size() - 1);
            }
        }
    }

    static class Solution2 {

        private Map<String, List<String>> map = new HashMap<>();

        public List<String> wordBreak(String s, List<String> wordDict) {
            List<String> backtrack = backtrack(s, new HashSet<>(wordDict));
            return backtrack;
        }


        private List<String> backtrack(String words, Set<String> dict) {
            List<String> result = map.get(words);
            if (result != null && result.size() > 0) return result;
            result = new ArrayList<>();
            for (int i = 1; i <= words.length(); i++) {
                String word = words.substring(0, i);
                if (dict.contains(word)) {
                    String remaining = words.substring(i);
                    List<String> list = map.get(remaining);
                    if (list == null) {
                        list = backtrack(remaining, dict);
                    }
                    if (list.size() == 0) {
                        if (word.length() == words.length()) {
                            result.add(word);
                        }
                    } else {
                        for (int j = 0; j < list.size(); j++) {
                            result.add(word + " " + list.get(j));
                        }
                    }
                }
            }
            map.put(words, result);
            return result;
        }

    }


    public static void main(String[] args) {
        Map<String, List<String>> cases = new LinkedHashMap<>();
        WordBreakII140 wordBreakII140 = new WordBreakII140();
        Solution2 solution2 = new Solution2();
        cases.put("catsanddog", Lists.newArrayList("cat", "cats", "and", "sand", "dog"));
//        cases.put("pineapplepenapple", Lists.newArrayList("apple", "pen", "applepen", "pine", "pineapple"));
//        cases.put("catsandog", Lists.newArrayList("cats", "dog", "sand", "and", "cat"));
//        cases.put("catsandog", Lists.newArrayList("cats", "dog", "sand", "and", "cat"));
        cases.put("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", Lists.newArrayList("a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa"));
        cases.forEach((k, v) -> {
//            List<String> result = wordBreakII140.wordBreak(k, v);
            List<String> result = solution2.wordBreak(k, v);
            System.out.println(k + "\t" + result);
        });
    }


    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<Integer>();
        for(int num: nums1) {
            set.add(num);
        }
        Set<Integer> set2 = new HashSet<Integer>();
        for(int num: nums2) {
            set2.add(num);
        }
        List<Integer> list = new ArrayList<>();
        Iterator<Integer> it = set.iterator();
        while(it.hasNext()){
            Integer val = it.next();
            if(set2.contains(val)) {
                list.add(val);
            }
        }
        return list.stream().mapToInt(value -> value).toArray();
    }
}
